package DoublePointSeries;

public class RemoveNthFromEnd_19_3 {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 双指针
        // 要删除倒数第n个节点，让fast移动n+1步
        // 然后让fast和slow同时移动，直到fast指向链表末尾。
        // 删掉slow所指向的next就可以了。

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode slow = dummyHead;
        ListNode fast = dummyHead;

        // fast先移动n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        // 不能返回head是因为如果是有一个节点，删除之后head就是空节点了
        return dummyHead.next;
    }
}
